package com.zxy.javaarithmetic.LinearList;

import com.zxy.javaarithmetic.Utils;

/**
 * @author : Shonn.Zhang
 * @email : shonn.zhang@mart.blue
 * @time : 2021/8/27 14:12
 * @desc : 插入排序(原地排序，稳定排序，时间复杂度O(n^2))
 *         将数组划分为已排序区间和未排序区间，从已排序区间的末尾向前搜索第一个小于等于插入值的位置i,则在i+1位置插入要插入的数
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = {6, 1, 2, 6, 9, 3, 4, 6, 10, 8};
        Utils.print(arr);
        insertSort(arr);
        Utils.print(arr);
    }

    private static void insertSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;

        int j, tmp;
        for (int i = 1; i < arr.length; i++) {
            tmp = arr[i];
            for (j = i - 1; j >= 0; j--) {
                if (arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] = tmp;
        }
    }

}
